package com.bm;

/**
 * Description: BM75 编辑距离(一)
 * 自己建个dp表 自己领悟
 *
 * @author weiruibai.vendor
 * Date: 2022/10/20 09:56
 */
public class BM75 {

    public static void main(String[] args) {
        String str1 = "nowcoder";
        String str2 = "new";
        System.out.println(editDistance(str1, str2));
    }

    public static int editDistance(String str1, String str2) {
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        int N = chars1.length + 1;
        int M = chars2.length + 1;
        int[][] dp = new int[N][M];
        for (int i = 0; i < N; i++) {
            dp[i][0] = i;
        }
        for (int i = 1; i < M; i++) {
            dp[0][i] = i;
        }
        // System.out.println("klsjflsa");
        for (int i = 1; i < N; i++) {
            for (int j = 1; j < M; j++) {
                try {
                    int v1 = dp[i - 1][j - 1] + (chars1[i - 1] == chars2[j - 1] ? 0 : 1);
                    int v2 = dp[i - 1][j] + 1;
                    int v3 = dp[i][j - 1] + 1;
                    dp[i][j] = Math.min(v1, Math.min(v2, v3));
                } catch (Exception e) {
                    System.out.println("-- :" + e);
                }
            }
        }

        return dp[N - 1][M - 1];
    }
}
